package com.ai.zuochengyun.phase01.class01;

import java.util.Arrays;

/**
 * 让数组中的数，<=X的在左边，>X的在右边
 * 当前数<=目标数，当前数和<=区的下一个数交换，<=区往右扩，当前数跳下一个
 * 当前数>目标数，当前数跳下一个
 */
public class Code11_PartitionAndQuickSort {

    public static void main(String[] args) {
        for (int i = 0; i < 10000; i++) {
            int size = (int) (Math.random() * 50) + 1;
            int[] arr = new int[size];
            for (int j = 0; j < size; j++) {
                arr[j] = (int) (Math.random() * 50) + 1;
            }
            quickSort1(arr);
            System.out.println(Arrays.toString(Arrays.stream(arr).toArray()));


            int[] arr2 = new int[arr.length];
            System.arraycopy(arr, 0, arr2, 0, arr.length);
            Arrays.sort(arr2);
            System.out.println(Arrays.toString(Arrays.stream(arr2).toArray()));

            if (!compare(arr, arr2)) {
                for (int j = 0; j < arr.length; j++) {
                    System.out.print(arr[i] + " ");
                }
                return;
            }
        }
    }

    private static boolean compare(int[] arr, int[] arr2) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    public static void quickSort1(int[] arr) {
        if (arr == null) {
            return;
        }
        // 让0到n-1范围有序
        process(arr, 0, arr.length - 1);
    }

    public static void process(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        // left到right范围进行排序
        int[] partition = partition(arr, left, right);
        int lt = partition[0] - 1;
        int gt = partition[1] + 1;
        // left到lt（小于区）范围进行排序
        process(arr, left, lt);
        // gt（大于区）到right范围进行排序
        process(arr, gt, right);
    }

    private static int[] partition(int[] arr, int left, int right) {
        if (left > right) {
            return new int[]{-1, -1};
        }
        if (left == right) {
            return new int[]{left, right};
        }

        // 在left和right范围内随机找到一个位置，和right位置的值交换
        int rand = (int) (Math.random() * (right - left));
        swap(arr, left + rand, right);

        // 小于区，初始位置在left - 1位置
        int lt = left - 1;
        // 大于区，初始位置在right位置，因为right位置的数先做为目标数，不参与排序
        int gt = right;
        int index = left;
        int target = arr[right];
        // 当前数不能撞上大于区
        while (index < gt) {
            int cur = arr[index];
            if (cur < target) {
                swap(arr, index++, ++lt);
            } else if (cur == target) {
                index++;
            } else {
                swap(arr, index, --gt);
            }
        }
        // 将right位置的数也进行排序，和大于区的第一个数进行交换
        swap(arr, right, gt);
        return new int[]{lt + 1, gt};
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}
